题目
题解
中心扩散
动态规划
动态规划的关键点:初始条件和状态转换方程。
设:s[l][r]表示字符串中下标L到R的位置
则有如下转态转换方程
s[l][r] = s[l+1][r-1] && (s[l] == s[r])
那初始状态呢
s[l][l] = ture
s[l][l+1] = (s[l] == s[l+1])
class Solution {
public:
string longestPalindrome(string s) {
vector<vector<bool>> v(s.size(),vector<bool>(s.size(),false));
string res;
for(int i = 0; i < v.size();++i)
{
for(int j = i; j < v.size();++j)
{
if(i == j)
v[i][j] = true;
else if(j-i == 1)
v[i][j] = s[i] == s[j] ? true : false;
}
}
//这里需要注意一点的是从后往前遍历,因为v[i][j] = v[i+1][j-1] && (s[i] == s[j]);会优先用到数组尾部的数据
for(int i = v.size()-1; i >= 0;--i)
{
for(int j = i; j < v.size();++j)
{
if(j-i > 1)
v[i][j] = v[i+1][j-1] && (s[i] == s[j]);
if(v[i][j] == true && j-i+1 > res.size())
res = s.substr(i,j-i+1);
}
}
return res;
}
};